/*
*
* 版权所有 Copyleft(c) 2005
* 刘炯个人工作室 Sharp-Mark Personal Studio
*
* 允许自由使用，复制，修改，传播和贩卖此源程序及其文档，而不必支付任何费用。
* 以上的版权信息必须出现在每一份复制品中。同时这份版权信息和许可声明
* 也必须出现在支持文档中。刘炯个人工作室不对此软件适于那种具体
* 用途做出任何阐述。此代码只作为代码本身提供对其品质不做任何保证。
*
*/

#include "../Shape/Polygon.h"

class CEdgeNode
{
public:
	CEdgeNode();
	CEdgeNode(float x, float dx, int y) : X(x), Dx(dx),Y(y){}
	float X;
	float Dx;
	int Y;	// 当标识AE的时候，Y表示Ymax；当表示NE时，Y表示Ymin
};

class CNewEdgeTable
{
public:
	CNewEdgeTable();
	CNewEdgeTable(int nodesNumber);
	~CNewEdgeTable();
	//EdgeNode** Link;
	std::vector< std::list< CEdgeNode >* > Links;
private:
	int _nodesNumber;
};

class CActiveEdgeTable
{
public:
	CActiveEdgeTable();
	std::list< CEdgeNode > Link;
	//int NodesNumber;
	void InsertNodes(std::list<CEdgeNode> * top);		// 按横坐标排列
private:
	//int _nodeNumber;
};

class CompareEdge
{
public:
	bool operator()(const CEdgeNode& n1, const CEdgeNode& n2) const
	{
		return (n1.X < n2.X);
	}
};

CEdgeNode::CEdgeNode(){}

CNewEdgeTable::CNewEdgeTable(int nodesNumber) : _nodesNumber(nodesNumber)
{
	Links = std::vector< std::list <CEdgeNode> *>(nodesNumber);

	for(std::vector< std::list<CEdgeNode> * >::iterator lp = Links.begin(); lp != Links.end(); lp++)
	{
		(*lp) = new std::list<CEdgeNode>;
	}
}

CNewEdgeTable::~CNewEdgeTable()
{
	for(std::vector< std::list<CEdgeNode> * >::iterator lp = Links.begin(); lp != Links.end();)
	{
		std::vector< std::list< CEdgeNode > * >::iterator delp = lp;
		lp++;
		delete (*delp);
	}
}
CNewEdgeTable::CNewEdgeTable(){}

CActiveEdgeTable::CActiveEdgeTable(){}

void CActiveEdgeTable::InsertNodes(std::list<CEdgeNode> * top)
{
	for (std::list<CEdgeNode>::iterator p = top->begin(); p != top->end(); ++p)
	{
		Link.push_back(*p);
		Link.sort(CompareEdge());
	}
}

//CEdgeNode CEdgeNode::operator-(const CEdgeNode& rhs) const
//{
//	return CEdgeNode(this->X - rhs.X, 0, 0);
//}
//CEdgeNode CEdgeNode::operator+(const CEdgeNode& rhs) const
//{
//	return CEdgeNode(this->X - rhs.X, 0, 0);
//}
//bool operator==(const CEdgeNode& lhs, const CEdgeNode& rhs)
//{
//	return (lhs.X == rhs.X);
//}
//bool operator<(const CEdgeNode& lhs, const CEdgeNode& rhs)
//{
//	return (lhs.X < rhs.X);
//}
//bool operator>(const CEdgeNode& lhs, const CEdgeNode& rhs)
//{
//	return (lhs.X > rhs.X);
//}

static void PolyFillEdgeScan(CPolygon& polygon, COLORREF color, CPaintDC& dc, CRect& rect)
{
	// 确定上下边界
	int bottom = rect.Height();
	int top = 0;

	for(int i = 0; i < polygon.Num; i++)
	{
		if( bottom >= polygon.Edges[i].yMin )
		{
			bottom = polygon.Edges[i].yMin;
		}

		if( top <= polygon.Edges[i].yMax )
		{
			top = polygon.Edges[i].yMax;
		}
	}


	CNewEdgeTable net(top - bottom + 1);			// 生成NewEdgeTable.

	// 扫描各条边
	int b = bottom;
	for(std::vector< std::list<CEdgeNode> * >::iterator vp = net.Links.begin(); vp != net.Links.end(); vp++)
	{
		for(int j = 0; j < polygon.Num; j++)
		{
			if(polygon.Edges[j].yMin == b)
			{
				(**vp).push_back(CEdgeNode((float)polygon.Edges[j].xMin,
					polygon.Edges[j].dx, polygon.Edges[j].yMax));
			}
		}
		b++;
	}

	CActiveEdgeTable aet;

	for(int i = 0; i <= top - bottom; i++ )
	{
		aet.InsertNodes(net.Links[i]);

		for(std::list< CEdgeNode >::iterator p = aet.Link.begin(); p != aet.Link.end(); ++p)
		{
			CEdgeNode& start = (*p);
			p++;
			if(p == aet.Link.end()) break;
			CEdgeNode& end = (*p);

			int y1, y2;
			int y = i + bottom;
			if(start.X == end.X)
			{
				y1 = polygon.GetEdgePointY((int)start.X, y, start.Dx);
				y2 = polygon.GetEdgePointY((int)end.X, y, end.Dx);

				if(start.Dx == 0 || end.Dx == 0)
				{
					int nextX1 = polygon.GetEdgePointX((int)start.X, y, 0);
					int nextX2 = polygon.GetEdgePointX((int)end.X, y, 0);
					if((++p) != aet.Link.end() && nextX1 != (*p).X && nextX2 != (*p).X)
					{
						for(int n = start.X + 1; n < end.X; n++)
						{
							dc.SetPixelV(n, i + bottom, color);
						}
					}
					p--;

				}
				else if(y1 > y && y2 > y)
				{
					for(int n = start.X + 1; n < end.X; n++)
					{
						dc.SetPixelV(n, i + bottom, color);
					}
				}
				else if(y1 > y || y2 > y)
				{
					p--;
				}
				else
				{
					continue;
				}
			}
			else
			{
				if(start.Dx == 0 || end.Dx == 0)
				{
					int nextX = polygon.GetEdgePointX((int)start.X, y, 0);

					if(end.X != nextX)
					{
						for(int n = start.X + 1; n < end.X; n++)
						{
							dc.SetPixelV(n, i + bottom, color);
						}
					}

					continue;
				}
				else
				{
					for(int n = int(start.X + 0.5) + 1; n < end.X; n++)
					{
						dc.SetPixelV(n, i + bottom, color);
					}
				}
			}
		}

		for(std::list<CEdgeNode>::iterator p = aet.Link.begin(); p != aet.Link.end();)
		{
			if ((*p).Y == (i + bottom))
			{
				std::list<CEdgeNode>::iterator delp = p;
				p++;
				aet.Link.erase(delp);
			}
			else
			{
				(*p).X += (*p).Dx;
				p++;
			}

		}

		aet.Link.sort(CompareEdge());
	}
}